//
//  maxSubSum.c
//  Chapter_1
//
//  Created by hao on 18/3/18.
//  Copyright © 2018年 hao. All rights reserved.
//

#include "maxSubSum.h"

// 返回3个整数中的最大值
int max1(int A, int B, int C )
{
    return A > B ? A > C ? A : C : B > C ? B : C;
}

// 分而治之 时间复杂度nLogn
int divideAndConquer(int list[], int left, int right)
{
    int maxLeftSum, maxRightSum; /* 存放左右子最大值 */
    int maxLeftBorderSum, maxRightBorderSum; /*存放跨分界线的结果*/
    
    int leftBorderSum, rightBorderSum; // 左右序列的累加
    
    if (left == right) { // 表示指向同一个值
        return list[left] > 0 ? : 0;
    }
    
    int center = (left+right)/2;
    // 获取左边的最大值
    maxLeftSum = divideAndConquer(list, left, center);
    // 获取右边的最大值
    maxRightSum = divideAndConquer(list, center+1, right);
    
    leftBorderSum = maxLeftBorderSum = 0;
    // 搜索计算左边的最大值
    for (int i = center; i >= left; i--) {
        leftBorderSum += list[i];
        if (leftBorderSum > maxLeftBorderSum) {
            maxLeftBorderSum = leftBorderSum;
        }
    }
    
    rightBorderSum = maxRightBorderSum = 0;
    /* 从中线向右扫描 */
    for (int i = center+1; i <= right; i++) {
        rightBorderSum += list[i];
        if (rightBorderSum > maxRightBorderSum) {
            maxRightBorderSum = rightBorderSum;
        }
    }
    
    printf("maxLeftSum = %d, maxRightSum = %d, (maxLeftValue+maxRightValue) = %d \n", maxLeftSum, maxRightSum, (maxLeftBorderSum+maxRightBorderSum));
    return max1(maxLeftSum, maxRightSum, (maxLeftBorderSum+maxRightBorderSum));
}

int maximumSubsequenceSum1(int series[], int count)
{
    return divideAndConquer(series, 0, count-1);
}

// 该算法时间复杂度n
int maximumSubsequenceSum2(int series[], int count)
{
    int maxSum, currentSum;
    maxSum = currentSum = 0;
    for (int i = 0; i < count; i++) {
        currentSum += series[i];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        } else if (currentSum < 0) {
            currentSum = 0;
        }
    }
    return maxSum;
}

